package org.example.myleet.p947;

import java.util.*;

public class Solution {
    /**
     * 103 ms
     */
    public int removeStones(int[][] stones) {
        UnionFind uf = new UnionFind();
        for (int i=0; i<stones.length; i++) {
            //将每个点加入到并查集中
            uf.union(new Point(stones[i]));
        }
        Set<Point> roots = new HashSet<>();
        for (Point p : uf.parent.keySet()) {
            roots.add(uf.find(p));
        }
        return stones.length - roots.size();
    }

    static class UnionFind {
        //x或y坐标的根节点map
        Map<Integer, Point> xRootMap = new HashMap<>();
        Map<Integer, Point> yRootMap = new HashMap<>();
        //并查集父节点记录map
        Map<Point, Point> parent = new HashMap<>();

        public Point find(Point p) {
            if (!parent.containsKey(p)) {
                //节点不存在时创建节点
                parent.put(p, p);
                return p;
            }
            //并查集通用操作，迭代法寻找父节点直到根节点（根节点的父节点还是根节点）
            Point point = parent.get(p);
            Point t;
            while (!point.equals(t = parent.get(point))) {
                parent.put(point, t);
                point = t;
            }
            return point;
        }

        /**
         * 将某个节点加入到并查集中
         */
        public void union(Point p) {
            //初始化一下节点p
            Point rootP = find(p);
            if (xRootMap.containsKey(p.x)) {
                //存在x轴相同的根节点，则根节点的根节点其父节点更新为新节点，所有连通的节点全部连接到新节点上
                Point xRoot = xRootMap.get(p.x);
                Point xRootRoot = find(xRoot);
                parent.put(xRootRoot, rootP);
                xRootMap.put(xRoot.x, rootP);
                yRootMap.put(xRoot.y, rootP);
                xRootMap.put(xRootRoot.x, rootP);
                yRootMap.put(xRootRoot.y, rootP);
            }
            if (yRootMap.containsKey(p.y)) {
                //同理
                Point yRoot = yRootMap.get(p.y);
                Point yRootRoot = find(yRoot);
                parent.put(yRootRoot, rootP);
                xRootMap.put(yRoot.x, rootP);
                yRootMap.put(yRoot.y, rootP);
                xRootMap.put(yRootRoot.x, rootP);
                yRootMap.put(yRootRoot.y, rootP);
            }
            //x轴y轴的位置标记这个根节点，便于连接到下一个入点
            xRootMap.put(p.x, rootP);
            yRootMap.put(p.y, rootP);
        }
    }

    static class Point {
        int x;
        int y;

        public Point(int[] point) {
            x = point[0];
            y = point[1];
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Point{");
            sb.append("x=").append(x);
            sb.append(", y=").append(y);
            sb.append('}');
            return sb.toString();
        }
    }
}
